In [1]:
from notebook.services.config import ConfigManager
from IPython.paths import locate_profile
cm = ConfigManager(profile_dir=locate_profile(get_ipython().profile))
cm.update('livereveal', {
'theme': 'solarized',
'transition': 'zoom',
'start_slideshow_at': 'selected',
})
Out[1]:
In [2]:
def ins_sort(k):
for i in range(1,len(k)): #since we want to swap an item with previous one, we start from 1
j = i #because we need 2 indexes as one will reduce and we do not want to affect i
while j > 0 and k[j] < k[j-1]: #j>0 since there is no value to the left of the 0 index
k[j], k[j-1] = k[j-1], k[j] # swap the items, if right one is smaller. (sometimes we use a temp variable)
j=j-1 #reduce j and repeat
return k
print(ins_sort([5,8,1,3,6,9]))
Merge sort is a sorting algorithm that works by splitting an array into subarrays, sorting the individual sub arrays and joining it back up into a single, sorted array.
This is known as a divide and conquer algorithm.
In [3]:
C = []
A = [1, 3]
B = [2, 4]
C.append(min(min(A), min(B)))
print(C)
In [4]:
A = [3]
B = [2, 4]
C.append(min(min(A), min(B)))
print(C)
In [5]:
A = [3]
B = [4]
C.append(min(min(A), min(B)))
print(C)
# nothing left in A, so just add what is left of B
C += B
print(C)
In [6]:
def merge_sort(x):
result = []
if len(x) < 2:
return x
mid = int(len(x)/2) # calculate mid point
y = merge_sort(x[:mid]) #split up to mid point and sort
z = merge_sort(x[mid:]) #get the rest of the mid point and sort
i = 0
j = 0
while i < len(y) and j < len(z): # loop through both lists
if y[i] > z[j]: #if left is more than right, add to result and increment index
result.append(z[j])
j += 1
else: #if right is more than left, add to result and increment right index
result.append(y[i])
i += 1
result += y[i:] #we can assume this is sorted, so we add the rest of the lists based on the index
result += z[j:]
return result
print(merge_sort([5,8,1,3,6,9]))
In [7]:
print(sorted([5, 100, 7, 2, 8149, 23, 19, 473]))
Python has sorting methods built into its standard library.
And it is pretty good!
In [8]:
import time
import random
small_sorted_list = [x for x in range(4)]
rev_small_sorted_list = small_sorted_list[::-1]
sorted_list = [x for x in range(1024)]
rev_sorted_list = sorted_list[::-1]
#Start timing
def time_to_sort(to_sort, print_string):
start = time.time()
to_sort.sort()
elapsed = time.time() - start
print(print_string.format(elapsed))
time_to_sort(small_sorted_list, "Sorted: {}")
time_to_sort(rev_small_sorted_list, "Reverse: {}")
time_to_sort([1,5,2,8,3], "Partially Sorted: {}")
time_to_sort([random.randint(0,1000) for r in range(1024)], "Random: {}")
Timsort (now used in Python, Java and Android) is a combination of the Merge Sort and Insertion Sort. In simple terms, it runs like this:
HOWEVER, when the list is smaller than a set size (the minrun) then it ignores the above method and just uses Insertion Sort.
This is what makes it so fast, it is known as an Adaptive Sort.
You answered it in the previous exercise:
Algorithms are not always consistently amazing.
They have a best case scenario, so they must have a worst case scenario too. Which means that most of the time, they will have an average case scenario.
The complexity of an algorithm describes how an algorithm performs based on these scenarios
So, let's work out the complexity of some operations:
print(n) - This is a constant and has no complexity, but what if we want to print n times?
for x in range(n):
print(x)
Now the operations depend on the size of N, so we call this O(n)
What about this?
for x in range(n):
for y in range(n):
print(x)
Now the run time depends on the size of N but it loops through N within N (Still with me)?
This makes the complexity O(n^2) or O(n*n)
Those of you that have read the Wikipedia article will have seen this, but let's go through the Bubble Sort.
First, a reminder of how it works:
def bubble_sort(input_list, index, end):
if index > end:
return(input_list)
if index == end:
recursive_sort(input_list, 0, end - 1)
elif len(input_list[index]) > len(input_list[index + 1]):
current = input_list[index]
print("Switching \"{0}\" at {1} for \"{2}\"".format(current, index, input_list[index + 1]))
input_list[index] = input_list[index + 1]
input_list[index + 1] = current
recursive_sort(input_list, index + 1, end)
return input_listBubble Sort is a bit unique in that the worst case and average case complexity is the same.
Regardless of what happens, the algorithm loops through every item in the list until there are no swaps to be made.
A reversed list or a randomly ordered requires the number of passes to be n * n, thus giving it the same average and worst case
Good: Detecting already sorted algorithms.
Bad: Everything else.